#include <dbg.h>
#include <gtest/gtest.h>
using namespace std;

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == nullptr || root == p || root == q) {
            return nullptr;
        }

        TreeNode* left = lowestCommonAncestor(root->left, p, q);  // 递归左子树
        TreeNode* right =
            lowestCommonAncestor(root->right, p, q);  // 递归右子树
        if (left && right) {                          // p q 分别在左右子树
            return root;                              // 根节点就是最近公共祖先
        }

        return left ? left : right;  // p q 都在左子树或右子树,
                                     // 最近公共祖先在左子树或右子树
    }
};

TEST(TEST1, lowestCommonAncestor) {
    Solution s;

    TreeNode* root = nullptr;
    TreeNode* p = nullptr;
    TreeNode* q = nullptr;
    TreeNode* ans = nullptr;

    root = new TreeNode(3);
    root->left = new TreeNode(5);
    root->right = new TreeNode(1);
    root->left->left = new TreeNode(6);
    root->left->right = new TreeNode(2);
    root->left->right->left = new TreeNode(7);
    root->left->right->right = new TreeNode(4);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(8);

    p = root->left;
    q = root->right;
    ans = s.lowestCommonAncestor(root, p, q);
    EXPECT_EQ(ans->val, 3);
}

TEST(TEST2, lowestCommonAncestor) {
    Solution s;

    TreeNode* root = nullptr;
    TreeNode* p = nullptr;
    TreeNode* q = nullptr;
    TreeNode* ans = nullptr;

    root = new TreeNode(3);
    root->left = new TreeNode(5);
    root->right = new TreeNode(1);
    root->left->left = new TreeNode(6);
    root->left->right = new TreeNode(2);
    root->left->right->left = new TreeNode(7);
    root->left->right->right = new TreeNode(4);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(8);

    p = root->left;
    q = root->left->right->right;
    ans = s.lowestCommonAncestor(root, p, q);
    EXPECT_EQ(ans->val, 5);
}

int main(int argc, char** argv) {
    ::testing::InitGoogleTest(&argc, argv);
    return RUN_ALL_TESTS();
}